UVa/11481 - Arrange the Numbers/explicación/e.tex

   1 \documentclass[10pt,letterpaper]{article}
   2
   3 %---------------------------------------------------------------
   4 \usepackage[utf8]{inputenc}
   5 \usepackage[spanish]{babel}
   6 \usepackage{listings}
   7 \usepackage[usenames,dvipsnames]{color}
   8 \usepackage{amsmath}
   9 \usepackage{amsthm}
  10 \usepackage{amssymb}
  11 %\usepackage{color}
  12 %---------------------------------------------------------------
  13
  14 \setlength{\topmargin}{-1.0in}
  15 \setlength{\textheight}{9.5in}
  16 \setlength{\evensidemargin}{0.0in}
  17 \setlength{\oddsidemargin}{0.0in}
  18 \setlength{\textwidth}{6.5in}
  19
  20 \begin{document}
  21
  22 La respuesta es
  23 $$
  24 {m \choose k} \cdot \displaystyle \sum_{i=0}^{m-k} (-1)^{i}  {m - k \choose i} (n-k-i)!
  25 $$
  26
  27 \bigskip
  28
  29 \textbf{Explicación:} Lo primero que hacemos es escoger los $k$ elementos que quedarán ``clavados'' en su sitio correcto. Esto se puede hacer de $ {m \choose k} $ maneras diferentes, pues cualquier subconjunto de $k$ elementos entre los primeros $m$ elementos sirve para este propósito. \\
  30 \\
  31 Ahora bien, por cada una de estas clavadas nos quedan $ n - k $ elementos por ubicar. Hay que hacerlo de manera que en las primeras $ m - k $ posiciones ningún elemento quede en su sitio, porque si sucede lo contrario entonces habrá mas elementos clavados en su sitio de los $k$ pedidos. Para contar cuántas permutaciones de $n-k$ elementos cumplen esto, utilizamos el principio de inclusión-exclusión\footnote {Bastante similar a la demostración del teorema 2, ``Número de permutaciones completas'', Sección 6.6: \textit{Aplicaciones del principio de inclusión-exclusión}, Capítulo 6: \textit{Técnicas avanzadas de recuento}, página 430, del libro \textbf{Matemáticas discretas y sus aplicaciones}, Kenneth Rosen, quinta edición, McGraw-Hill.}. El resultado es la sumatoria que multiplica a ${ m \choose k}$.\\
  32
  33 \begin{proof}{}
  34 Decimos que una permutación tiene la propiedad $P_{i}$ si deja en su sitio el elemento $i$. El número que se busca es el número de permutaciones de $n - k$ elementos que no tiene la propiedad $P_{i}$ para $i=1, 2, \cdots , m - k$ y lo denotamos $ D = N(\bar{P_{1}} \bar{P_{2}} \cdots \bar{P}_{m-k}) $. Aplicando el principio de inclusión-exclusión tenemos que:\\
  35 $$
  36 D = N - \sum_{i}{N(P_{i})} + \sum_{i < j}{N(P_{i}P_{j})} - \sum_{i < j < k}{N(P_{i}P_{j}P_{k})} + \cdots + (-1)^{m-k}N(P_{1}P_{2} \cdots P_{m-k})
  37 $$
  38
  39 Vemos que $$ N = (n-k)! $$ pues $N$ es la cantidad de permutaciones posibles.\\
  40 Así mismo, $$ \sum_{i}{N(P_{i})} = { m - k \choose 1 } (n -k -1)! $$ Esto es, clavamos un sólo elemento de los primeros $m - k$ posibles, y el resto los permutamos de cualquier manera posible. Pero al restar estos elementos, restamos dos veces las permutaciones que tienen dos elementos fijos, así que las volvemos a sumar:
  41 $$\sum_{i < j}{N(P_{i}P_{j})} = { m - k \choose 2 } (n -k -2)! $$
  42 Esto es, clavamos dos elementos y el resto los permutamos de cualquier manera posible.\\
  43 Y en general,
  44 $$\sum{N(P_{i_{1}}P_{i_{2}} \cdots P_{i_{r}})} = { m - k \choose r } (n -k -r)! $$
  45 Reemplazando estos términos en la ecuación original, obtenemos
  46 $$
  47 D = N - \sum_{i}{N(P_{i})} + \sum_{i < j}{N(P_{i}P_{j})} - \sum_{i < j < k}{N(P_{i}P_{j}P_{k})} + \cdots + (-1)^{m-k}N(P_{1}P_{2} \cdots P_{m-k}) $$
  48 $$
  49 = (n - k)! - { m - k \choose 1 } (n -k -1)! +  { m - k \choose 2 } (n -k -2)! -
  50  \cdots + (-1)^{m-k}  { m - k \choose m - k } (n -k -(m - k))!
  51 $$
  52 $$
  53 = \sum_{i=0}^{m-k} (-1)^{i}  {m - k \choose i} (n-k-i)!
  54 $$
  55 \end{proof}
  56 \end{document}